package leetcode.editor.cn;

//[200]岛屿数量
public class NumberOfIslands200 {
    public static void main(String[] args) {
        Solution solution = new NumberOfIslands200().new Solution();

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //dfs	执行耗时:2 ms,击败了99.99% 的Java用户 //	内存消耗:48.2 MB,击败了62.80% 的Java用户
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length < 1 || grid[0] == null || grid[0].length < 1) return 0;
            int count = 0;
            int mlen = grid.length;
            int nlen = grid[0].length;
            for (int i = 0; i < mlen; i++) {
                for (int j = 0; j < nlen; j++) {
                    if (grid[i][j] == '1') {
                        count++;
                        dfs(grid, mlen, nlen, i, j);
                    }
                }
            }
            return count;
        }

        private void dfs(char[][] grid, int mlen, int nlen, int i, int j) {
            if (i < 0 || i >= mlen || j < 0 || j >= nlen) return;
            if (grid[i][j] == '1') {
                grid[i][j] = 0;
            }else {
                return;
            }
            dfs(grid, mlen, nlen, i - 1, j);
            dfs(grid, mlen, nlen, i + 1, j);
            dfs(grid, mlen, nlen, i, j + 1);
            dfs(grid, mlen, nlen, i, j - 1);
        }


    }
//leetcode submit region end(Prohibit modification and deletion)

}